package NiuKe.StackandQueqe;
import java.util.*;

/**
 * 堆栈队列习题
 * https://www.nowcoder.com/exam/oj?page=1&tab=%E7%AE%97%E6%B3%95%E7%AF%87&topicId=295
 */
/*class stack{
    int val;
    stack next;
}*/

public class Solution {

    //用两个栈实现队列
   /* 1：用两个栈来实现一个队列，使用n个元素来完成 n 次在队列尾部插入整数(push)和n次在队列头部删除整数(pop)的功能。
    队列中的元素为int类型。保证操作合法，即保证pop操作时队列内已有元素。*/
   /* Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();

    public void push(int node) {
        stack1.push(node);

    }

    public int pop() {
        if (stack1==null)return -1;
        while (!stack1.isEmpty()){
            int a=stack1.pop();
            stack2.push(a);
        }
        int count=stack2.pop();
        while (!stack2.isEmpty()){
            int a=stack2.pop();
            stack1.push(a);
        }
        return count;
    }*/


//    包含min函数的栈
//    2：定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的 min 函数，
//    输入操作时保证 pop、top 和 min 函数操作时，栈中一定有元素。
   /* Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();
    public void push(int node) {
        stack1.push(node);
    }

    public void pop() {
        if (stack1==null)return;
        stack1.pop();
    }

    public int top() {
        if (stack1==null)return -1;
        return stack1.peek();
    }

    public int min() {
        if (stack1==null)return -1;
        int min=Integer.MAX_VALUE;
        while (!stack1.isEmpty()){
            int a=stack1.pop();
            if (min>a)min=a;
            stack2.push(a);
        }
        while (!stack2.isEmpty()){
            int a=stack2.pop();
            stack1.push(a);
        }
        return min;
    }*/

   /* 有效括号序列
    3:给出一个仅包含字符'(',')','{','}','['和']',的字符串，判断给出的字符串是否是合法的括号序列
    括号必须以正确的顺序关闭，"()"和"()[]{}"都是合法的括号序列，但"(]"和"([)]"不合法。
    解题思路：如果是左括号就入栈，右括号就出栈（ps：总感觉写过，但为什么我没记录呢？）*/
   public boolean isValid (String s) {
       if (s==null)return false;
       Stack<Character> stack1 = new Stack<Character>();
       for (int i = 0; i < s.length(); i++) {
           if(s.charAt(i) == '(') stack1.push(')');
           else if(s.charAt(i) == '[') stack1.push(']');
           else if(s.charAt(i) == '{') stack1.push('}');
           else if(stack1.isEmpty() || stack1.pop() != s.charAt(i))
               return false;
       }
      return stack1.isEmpty();
   }


   /* 滑动窗口的最大值
    4:给定一个长度为 n 的数组 num 和滑动窗口的大小 size ，找出所有滑动窗口里数值的最大值。
    解题思路：利用双指针来解决*/
   public static ArrayList<Integer> maxInWindows(int [] num, int size) {
       ArrayList<Integer> list=new ArrayList<>();
       int j=size-1;
       int max=0;
       for (int i = 0; i < num.length; i++) {
           if (max<num[i]){
               max=num[i];
           }
           if (j==0){
               list.add(max);
               max=0;
               continue;
           }
           if (i==j && j<num.length){
               list.add(max);
               max=0;
               i=j-size+1;
               j++;
           }
       }
       return list;
   }
    /*最小的K个数
    5:给定一个长度为 n 的可能有重复值的数组，找出其中不去重的最小的 k 个数。*/
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        //排除特殊情况
        if(k == 0 || input.length == 0)
            return res;
        //大根堆
        PriorityQueue<Integer> q = new PriorityQueue<>(k, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2-o1;
            }
        });
        //构建一个k个大小的堆
        for(int i = 0; i < k; i++)
            q.offer(input[i]);
        for(int i = k; i < input.length; i++){
            //较小元素入堆
            if(q.peek() > input[i]){
                q.poll();
                q.offer(input[i]);
            }
        }
        //堆中元素取出入数组
        for(int i = 0; i < k; i++)
            res.add(q.poll());
        return res;
    }
//    寻找第K大
//    6:有一个整数数组，请你根据快速排序的思路，找出数组中第 k 大的数。
//    解题思路：topK问题
    public static int findKth(int[] a, int n, int K) {
        PriorityQueue<Integer> maxHeap=new PriorityQueue<>(K, new Comparator<Integer>() {
            //创建一个大小为K的小根堆
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1-o2;//大根堆o2-o1;
            }
        });
        for (int i = 0; i < a.length; i++) {
            if (maxHeap.size()<K){
                maxHeap.offer(a[i]);
            }else{
                //3,从k+1个元素开始，每个元素与k顶元素进行比较
                int top=maxHeap.peek();
                if (top<a[i]){
                    //3.1先弹出后进来
                    maxHeap.poll();
                    maxHeap.offer(a[i]);
                }
            }
        }
        return maxHeap.poll();
    }

   /* 数据流中的中位数
    如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。
    如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。
    */
    //小顶堆，元素数值都比大顶堆大
    private PriorityQueue<Integer> max = new PriorityQueue<>();
    //大顶堆，元素数值较小
    private PriorityQueue<Integer> min = new PriorityQueue<>((o1, o2)->o2.compareTo(o1));
    //维护两个堆，取两个堆顶部即与中位数相关
    public void Insert(Integer num) {
        //先加入较小部分
        min.offer(num);
        //将较小部分的最大值取出，送入到较大部分
        max.offer(min.poll());
        //平衡两个堆的数量
        if(min.size() < max.size())
            min.offer(max.poll());
    }

    public Double GetMedian() {
        //奇数个
        if(min.size() > max.size())
            return (double)min.peek();
        else
            //偶数个
            return (double)(min.peek() + max.peek()) / 2;
    }





   /* 表达式求值
    7:请写一个整数计算器，支持加减乘三种运算和括号。
    解题思路:双栈表达式*/









}


